import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author 12629
 * @Description：
 */
class Intcmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1,Integer o2) {
        return o2.compareTo(o1);
    }
}
public class TestHeap {
    private int UseSize;
    private int[] elem;
    private static final int DefaultCapacity = 11;

    public TestHeap() {
        elem = new int[DefaultCapacity];

    }

    public TestHeap(int k) {
        elem = new int[k];

    }

    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            UseSize++;
        }
    }

    public void createHeap() {
        for (int parent = UseSize - 1 - 1 >> 1; parent >= 0; parent--) {
            shiftDown(parent, UseSize);
        }

    }

    private void shiftDown(int parent, int usedSize) {
        int child = parent * 2 + 1;
        while (child < usedSize) {
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }
        }

    }

    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }


    public void offer(int val) {
        if (isFull()) {
            Arrays.copyOf(elem, UseSize * 2);
        }

        elem[UseSize] = val;
        UseSize++;
        shiftUp(UseSize - 1);

    }

    private void shiftUp(int child) {
        int parent = child - 1 >> 1;
        while (parent >= 0) {
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent;
                parent = child - 1 >> 1;
            } else {
                break;
            }
        }

    }

    public boolean isFull() {
        return elem.length == UseSize;

    }

    public int poll() {
        int tmp = elem[0];
        swap(0, UseSize - 1);
        UseSize--;
        shiftDown(0, UseSize);
        return tmp;
    }

        public void heapSort() {
            int end = UseSize - 1;
            while (end > 0) {
                swap(0, end);
                shiftDown(0, end);
                end--;
            }
        }



    public int[] maxestK(int[] arr, int k){
        int[]ret=new int[k];
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(arr.length);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i <arr.length ; i++) {
            int tmp=priorityQueue.peek();
            if(tmp<arr[i]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;


    }
    public int peek(){

        return elem[0];
    }
    public int[] smallestK(int[] arr, int k){
        int []ret=new int[k];
        if(arr==null||k<=0){
            return ret;
        }
        PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(new Intcmp1());
        //建立k个数的堆，priority默认是小堆，要实现弹出最小的k个数要建立大堆！
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //如果arr[i]<priority.peek() 那就把priority.poll() 然后再priority.add();
        //类似于末尾淘汰制每次都是把三个当中最大的淘汰了！
        for (int i = k; i < arr.length; i++) {
            int top=priorityQueue.peek();
            if(top>arr[i]){
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();

        }
        return ret;
    }


}
